# 计数排序
# 2022-5-18
from utils.array_utils import check_all

def countsort_01(l):
    """ 将整型列表 排序
    只支持自然数"""
    max_value = max(l)
    bucket = (max_value + 1) * [0]
    for i in l:
        bucket[i] += 1

    # i是bucket列表的索引
    index = 0
    for i in range(max_value + 1):
        if bucket[i] == 0:
            continue
        # j 是当前索引的value, 如果大于1,则说明有多个值
        for j in range(bucket[i]):
            l[index] = i
            index += 1
        # print(i, bucket[i])
    # print(l)
    return l


def countsort_02(l):
    """ 将整型列表 排序
    支持所有整数"""
    if len(l) <2:
        return l
    min_value = min(l)
    if min_value < 0:
        for i in range(len(l)):
            # 将每个值都加上最小的负数值, 变成大于等于零
            l[i] -= min_value
    max_value = max(l)
    # 入桶
    bucket = [0] * (max_value + 1)
    for index in l:
        bucket[index] += 1
    # print(bucket)
    # 出桶
    index = 0
    for i in range(len(bucket)):
        for num in range(bucket[i]):
            # 将每个数还原
            l[index] = i + min_value
            index += 1
    return l


if __name__ == '__main__':
    ll = [49, 10, 96, 78, 57, 33, 66, 21, 49, 10, 96]
    countsort_01(ll)
    print(ll)
    ll = [49, 10, 96, -78, 57, 33, 66, 21, 49, -10, 96]
    print(countsort_02(ll))
    check_all(countsort_02, 100)
